//给出一个非空的整数数组，返回其中前k个出现最频繁的元素。
//
//        Example
//
//        [1,1,1,2,2,3]，k = 2，输出[1,2]
//
//        如果n是数组的大小，要求给出时间复杂度小于O(n log n)的算法。

//参考资料： https://zhuanlan.zhihu.com/p/32984123?group_id=936571009650548736


import java.util.ArrayList;
import java.util.HashMap;

public class Prog5 {
    public static void main(String[] args) {
        int[] num1 = {1,2,3,5,2,3,5,7,7,7,5,7};
        ArrayList<Integer> nums1 = topK(num1,4);
        System.out.println(nums1);
        int[] num2 = {1,1,1,2,2,3};
        ArrayList<Integer> nums2 = topK(num2,2);
        System.out.println(nums2);
    }
    private static  ArrayList<Integer> topK(int[] numbers , int k){
        HashMap<Integer, Integer> map = new HashMap<>();
        //构造一个链表来放map中的key；
        ArrayList<ArrayList<Integer>> keyList = new ArrayList<>();
        for(int i = 0; i<numbers.length; i++){
            Integer count = map.get(numbers[i]);
            if(count == null){
                count = 0;
            }
            map.put(numbers[i], count+1);
            ArrayList<Integer> temp = new ArrayList<>();
            keyList.add(temp);
        }


        for(int key:map.keySet()){
            //map中数出现的次数；
            int a = map.get(key);
            keyList.get(a).add(key);
        }
        ArrayList<Integer> res = new ArrayList<>();
        for(int i=keyList.size()-1; i>=0; i--){
            if(keyList.get(i) != null) {
                res.addAll(keyList.get(i));
            }
            if(res.size() >= k) {
                break;
            }
        }
        return res;
    }
}


